A Distributed Tracking Algorithm for Reconstruction of Graph Signals

摘要

The rapid development of signal processing on graphs provides a newperspective for processing large-scale data associated with irregular domains.In many practical applications, it is necessary to handle massive data setsthrough complex networks, in which most nodes have limited computing power.Designing efficient distributed algorithms is critical for this task. Thispaper focuses on the distributed reconstruction of a time-varying bandlimitedgraph signal based on observations sampled at a subset of selected nodes. Adistributed least square reconstruction (DLSR) algorithm is proposed to recoverthe unknown signal iteratively, by allowing neighboring nodes to communicatewith one another and make fast updates. DLSR uses a decay scheme to annihilatethe out-of-band energy occurring in the reconstruction process, which isinevitably caused by the transmission delay in distributed systems. Proof ofconvergence and error bounds for DLSR are provided in this paper, suggestingthat the algorithm is able to track time-varying graph signals and perfectlyreconstruct time-invariant signals. The DLSR algorithm is numericallyexperimented with synthetic data and real-world sensor network data, whichverifies its ability in tracking slowly time-varying graph signals.